#include<bits/stdc++.h>
using namespace std;

typedef struct node {
    char data;
    struct node* left;
    struct node* right;
}treenode;

void createtree(treenode* root, string s) {//建立二叉树
    root->data = s[0];
    int toward = 0;
    stack<treenode*>arr;//用队列存放元素
    arr.push(root);
    for (int i = 1; i < s.size(); i++) {
        if (s[i] == '(') {
            toward = 1;
        }
        else if (s[i] == ')') {
            arr.pop();
        }
        else if (s[i] == ',') {
            toward = 2;
            if (arr.size() != 1 && s[i - 1] != '(') {
                arr.pop();
            }
        }
        else {
            treenode* newnode = new treenode;
            newnode->left = newnode->right = NULL;
            if (toward == 1) {//左孩子
                arr.top()->left = newnode;
                newnode->data = s[i];
                arr.push(newnode);
            }
            else {//右孩子
                arr.top()->right = newnode;
                newnode->data = s[i];
                arr.push(newnode);
            }
        }
    }
}

void putouttree(treenode* root) //输出二叉树
{
    if (root != NULL)
    {
        printf("%c", root->data);
        if (root->left != NULL || root->right != NULL)
        {
            printf("(");
            putouttree(root->left);
            if (root->right != NULL)
                printf(",");
            putouttree(root->right);
            printf(")");
        }
    }
}

treenode* searchChild(treenode* root,char target) {//层次遍历寻找节点
    queue<treenode*>q;
    q.push(root);
    while (!q.empty()) {
        int length = q.size();
        for (int i = 0; i < length; i++) {
            root = q.front();
            q.pop();
            if (root->data == target) { return root; }
            if (root->left) { q.push(root->left); }
            if (root->right) { q.push(root->right); }
        }
    }
}


int depth(treenode* node) {//求深度
    if (node == NULL) { return 0; }
    return max(depth(node->left), depth(node->right)) + 1;
}

void devastateTree(treenode* node) {//销毁树
    if (node != NULL) {
        devastateTree(node->left);
        devastateTree(node->right);
        free(node);
    }
}

int main() {
    string tree = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
    treenode* root = new treenode;
    createtree(root, tree);//建树
    cout << "输出树：";
    putouttree(root);//输出树
    cout << endl;
    cout << "H节点的左孩子为：" << searchChild(root, 'H')->left->data << endl;
    cout << "H节点的右孩子为：" << searchChild(root, 'H')->right->data << endl;
    cout << "二叉树的高度为：" << depth(root);
    devastateTree(root);
    return 0;
}
